/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2023-02-04
 * Time: 21:16
 */
public class Day15 {
    //717.1比特与2比特
    public boolean isOneBitCharacter(int[] bits) {
        int start = 0;
        while (start < bits.length - 1) {
            if (bits[start] == 0){
                start++;
            }else{
                start += 2;
            }
        }
        return start == bits.length - 1;
    }
    //724.寻找数组的中心下标
    public int pivotIndex(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            if (ret == sum - ret - nums[i]){
                return i;
            }else{
                ret += nums[i];
            }
        }
        return -1;
    }
    //733.图像渲染
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int oldColor = image[sr][sc];
        DFS(image, sr, sc, color, oldColor);
        return image;
    }
    public void DFS(int[][] image, int x, int y, int newColor, int oldColor){
        if (x < 0 || x >= image.length || y < 0 || y >= image[0].length){
            return;
        }
        if (image[x][y] != oldColor || image[x][y] == newColor){
            return;
        }
        image[x][y] = newColor;
        DFS(image, x - 1, y, newColor, oldColor);
        DFS(image, x + 1, y, newColor, oldColor);
        DFS(image, x, y - 1, newColor, oldColor);
        DFS(image, x, y + 1, newColor, oldColor);
    }
    //744.寻找比目标字母大的最小字母
    public char nextGreatestLetter(char[] letters, char target) {
        char c = 0;
        for (int i = 0; i < letters.length; i++) {
            if (letters[i] > target) {
                return letters[i];
            }
        }
        return letters[0];
    }
    //746.使用最小的花费爬楼梯
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];

        dp[0] = dp[1] = 0;
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
    //747.至少是其它数字两倍的最大数
    public int dominantIndex(int[] nums) {
        int max = 0;
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            if (max < nums[i]){
                max = nums[i];
                ret = i;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (i != ret && max < nums[i] * 2){
                return -1;
            }
        }
        return ret;
    }
}





















